1. Field
The invention relates in general to Internet Security and, in particular to detection of denial of service (DoS) attacks and distributed denial of service (DDoS) attacks.
2. Related Art
In recent years, denial of service (DoS) attacks and distributed denial of service (DDoS) attack has become a major security threat to Internet service. A DoS attack and DDoS attack can completely consume the resources of a server, which will be unable to provide services for legitimate users. With the exponential increase of Internet-based e-business and e-commence, the damage of DoS attacks and DDoS attacks is becoming more and more significant. Therefore, how to handle DoS attacks and DDoS attacks and protect the access of legitimate users has become a crucial challenge and has attracted the attention f both the industry and academia.
Due to the readily available tools and its simple nature, flooding packets is the most common and effective DoS attack. While flooding tools have been becoming more sophisticated, they have been getting easier to use. An adversary without much knowledge of programming can download a flooding tool and then launch a DoS attack. The flooding traffic of a DoS attack may originate from either a single source or multiple sources. We call the latter case a distributed denial of service (DDoS) attack. Briefly, a DDoS attack works as follows. An attacker sends control packets to the previously-compromised flooding sources, instructing them to target at a given victim. The flooding sources then collectively generate and send an excessive number of flooding packets to the victim, but with fake and randomized source addresses, so that the victim cannot locate the flooding sources. To foil DoS attacks, researchers have designed and implemented a number of countermeasures. In general, the countermeasures of DoS attacks can be classified into three different categories: detection, defense (or mitigation), and IP trace-back mechanisms. Detecting DoS attacks in real time is the first step of combating DoS attacks. An automated and fast detection is essential to the protection against DoS attacks. Upon timely detection of a DoS attack, more sophisticated defense mechanisms will be triggered to shield victim servers or link bandwidth from DoS traffic, and block the prorogation of DDoS traffic at routers. At the same time, we can perform more expensive IP trace-back to single out flooding sources. Unlike defense and trace-back mechanisms, detection itself should be an always-on function with little overhead, causing minimal disruption to normal operations and withstanding any flooding attacks. Basically, detecting DoS attacks belongs to network-based intrusion detection. A network-based intrusion detection system (NIDS) is based on the idea that an intruder's behavior will be noticeably different from that of a legitimate user and that many unauthorized actions are detectable. A commonly used detection approach is either signature-based or anomaly-based. A signature-based NIDS inspects the passing traffic and searches for matches against already-known malicious patterns. A key advantage of signature-based detection algorithms is their high degree of accuracy in detecting known attacks and their variations. Their obvious drawback is the inability to detect attacks whose instances have not yet been observed. Anomaly detection approaches, on the other hand, build models of normal data and detect deviations from the normal model in observed data. Anomaly detection have the advantage that they can detect new types of attacks as deviations from normal usage. However, anomaly detection schemes suffer from a high rate of false alarms. This occurs primarily because previously unseen (yet legitimate) system behaviors are also recognized as anomalies, and hence flagged as potential attacks.
In the literature, there are a number of anti-DoS/DDoS systems, which can be generally categorized into host-based systems and network-based systems. Examples can be found in Mirkovic et. al. “A taconomy of DDoS attack and DDoS defense mechanism,” ACM SIGCOMM Computer Communications Review, vol. 34, no. 2, p. 39, 2004 and Chen et. al. “Characterization of defense mechanisms against distributed denial of service attacks,” 2003, submitted to Computers and Security. In host-based anti-DoS/DDoS systems, services can be protected by using firewall and intrusion detection system (IDS), and/or by applying carefully designed the service system, for example, a service system that includes a server farm and a load balancer. Although this approach can clearly protect the server system, it may not be efficient to protect legitimate users because the attack traffic has utilize a huge amount of resources in the network and because it is very difficult for the host to distinguish attack traffic from legitimate traffic in many circumstance.
With network-based anti-DoS/DDoS systems, on the other hand, the DoS/DDoS traffic can be filtered before it reaches the edge router that connects the potential victim. In this manner, the network-based anti-DoS/DDoS system is more efficient. Nevertheless, a network-based system is more difficult to be implemented since it may require the coordination of a huge number of elements in the Internet service provider (ISP) network, such as core routers, edge routers, and network management systems. In the present invention, we focus on the network-based anti-DoS/DDoS system for the ISP networks.
From the network perspective, an anti-DoS/DDoS system includes two major components: the detection system and the defense system. The detection system is responsible to report the occurrence of an ongoing DoS/DDoS attacks and to identify the attack sources. Apparently, to detect the attacks, a system can be implemented at the edge router that connects to the victim network. Similar to the host-based anti-DoS/DDoS systems, this detection system can be built on firewall and IDS systems. However, such an approach has the same drawback as that of the host-based systems. Clearly, it is more desirable to detect DoS/DDoS attacks at locations that are closer to the attack source. In the literature, Savage et. al. “Practical network support for ip traceback,” Proc. of ACM SIGCOMM'2000, August 2000. discusses the most common approach to identify the attack sources is IP traceback, in which the route of an incoming IP packet and/or the address of the edge router that forwarded this packet to the core network can be stored in IP packets. Unfortunately, such kinds of schemes require a global deployment and the modification of existing IP forwarding mechanism, for example, modifying the IP header, which is a difficult task, if not impossible.
The defense system is responsible to react to the attacks. Typically, depending on the information that can be provided by the detection system, defense can be classified into packet filtering and rate limiting. Examples can be found in Chen et. al. “Perimeter-based defense against high bandwidth DDoS attacks,” IEEE Transaction on Parallel Distributed Systems 2005. If the identification system can provide exact signature of attack traffic, then all packets that belong to the attack traffic will be directly blocked. On the other hand, if the identification system can only provide limited information, then the defense system can only limit the rate of potential attack traffic, which means that a portion of attack traffic will still be able to reach the victim and that some legitimate traffic will be mistakenly filtered.
From the discussion above, we can observe that the efficiency of the whole anti-DoS/DDoS system is highly dependent on the performance of the detection system. However, many existing schemes may require the modification of existing packet forwarding mechanism, such as IP traceback. More importantly, we observe that existing schemes ignore the characteristics of DDoS attacks, namely, the spatial and temporal correlation of the attack traffic.
Moreover anomaly detection algorithms need to be adaptive, which means they must be able to cope with constantly changing network conditions. Therefore, sophisticated traffic analysis is required to manage the strong non-stationary behavior of normal Internet traffic and at the same time distinguish between natural variations in traffic profiles, such as changed usage patterns between day and night, week-days and weekend or a flash-crowd to a web-site, and truly anomalous traffic variations, such as DDoS attacks. Second, the algorithms need to show a good trade-off between false positive/negative ratio and detection lag (time interval between the time at which the attack starts and the time at which the anomaly is detected). Third, the algorithms need to be computationally simple because of the multi-Gigabit per second (Gbps) links used by most of the carriers today and limited memory usage for on-fly information storage. Forth, the algorithms should detect both low and high-volume attacks. Most of the anomaly detection algorithms proposed usually handles the high-volume attack but their performance degrades severely as soon as the attacks rate drops below a specific threshold becoming almost undistinguishable with “Internet noise”. To gain a thorough picture of the overall traffic in a network, it is important for an adaptive anomaly detection solution to see the complete traffic profiles. Therefore, to handle the typical large, distributed networks of carriers and service providers, anomaly detection solutions need to be deployable such that a large number of links must be monitored in a cost-effective, yet scalable manner. Moreover, in order to detect low-volume attacks, the algorithm must extract and correlate a few key features that represent sufficiently well normal traffic behavior such to guarantee a fast and efficient detection of anomalies in their infancy stage.
In the literature, Wang et. al. “Detecting SYN flooding attacks,” Proc. IEEE INFOCOM'2002 New York City N.Y., June 2002, pp. 1530-1539 proposed to detect TCP SYN flood by using the ratio of the number of TCP SYN packets and the number of TCP FIN and RST packets. Ideally, if there are no SYN flood attacks, this ratio will be close to 1 in a sufficiently long duration, since most TCP sessions begin with a SYN packet and end with a FIN packet. However, one of the main difficulties of this scheme is that the duration of TCP sessions can be very large, which means that the ratio may not be close to 1 in a long period. To overcome this problem, Wang et. al. “Change point monitoring for the detection of dos attacks,” IEEE Transactions on Dependable and Secure Computing, no. 4 pp. 193-208, October 2004 proposed to use the ratio of the number of SYN packets and the number of SYN/ACK packets on the other direction, since the appearance of SYN and the corresponding SYN/ACK packets is the round trip time of the connection, which has much less variation. Nevertheless, this scheme can only be deployed at the location that is close to the attacker and can only detect SYN attack with spoofed source IP address.
It is well known that most of the DDoS attacks are characterized by using spoofed source IP addresses. Moreover, the number of packets from the same spoofed source IP addresses is relatively small, compared to the number of packets of a real session. Consequently, to generate a certain amount of attacks, the number of IP addresses will be large. Based on this assumption, Peng et. al. proposed to use the ratio of new IP address to detect attacks with spoofed source addresses in “Protection from distributed denial of services attacks using history based IP filtering,” Proc. IEEE ICC 2003, Anchorage, Ak. May 2003, pp. 482-486 and “Detecting distributed denial of services attacks using source IP address monitoring,” Department of Computer Science and Software Engineering, The University of Melbourne, Tech. Rep., 2002: http://www.cs.mu.oz.au/˜tpeng. In this scheme, a database is required to store the information of all IP addresses that appeared in a certain period, which means that the memory requirement is very large for large-scale Internet.
In addition to monitor the feature data such as the ratio of the number of TCP SYN packets and the number of TCP FIN and RST packets or the ratio of the number of SYN packets and the number of SYN/ACK packets on the other direction, another important issue is how to detect attacks or anomalies based on the observed feature data. In the literature, a number of existing studies suggested to use the statistical method, in particular, the change-point algorithm in Wang et. al. “Detecting SYN flooding attacks,” Proc. IEEE INFOCOM'2002 New York City N.Y., June 2002, pp. 1530-1539, Peng et. al. “Detecting distributed denial of services attacks using source IP address monitoring,” Department of Computer Science and Software Engineering, The University of Melbourne, Tech. Rep., 2002: http://www.cs.mu.oz.au/˜tpeng and Blazek et. al. “A novel approach to detection of “denial-of-service” attacks via adaptive sequential and batch-sequential change-point detection methods,” Proc. IEEE Workshop on Information Assurance and Security, West Point, N.Y., June 2001, pp. 220-226. The key idea behind the change-point algorithm is based on the observation that an attack leads to relatively abrupt changes in statistical models of traffic compared to the “normal mode”. These changes occur at unknown points in time and should be detected “as soon as possible”. Therefore, the problem of detecting an attack can be formulated and solved as a change-point detection problem: detect a change with a fixed delay (batch approach) or minimal average delay (sequential approach) with a minimum ratio of false alarm. However, we notice that in all these studies the parameters of the change-point algorithms are fixed and no comprehensive performance studies are provided. Moreover, these studies only consider one change, i.e. from normal to abnormal state. In practice, this approach may lead to significant false alarms after the finish of attacks.
Therefore, there is a need for a Robust and Efficient Detection scheme of DDoS Attacks for large-scale Internet.